The transmission of data through a noisy channel could introduce errors into the data stream. In order to reduce the amount of errors in the transmitted sequence and to avoid retransmissions coding techniques have been developed that provide the ability to detect and correct errors in a sequence. This is achieved usually through the addition of redundant information as part of the transmission. Here the term transmission is used broadly to include transfer of data through different types of medium. This can include communication mediums such as those used in wired, wireless, satellite, and other technologies. This can also include storage mediums such as magnetic, semiconductor, and other types of memory.
Some of the most popular and powerful coding techniques use convolutional codes either standalone or in more complex arrangements that include multiple codes, such as Parallel concatenated Convolutional Codes (PCCC or Turbo), Serially Concatenated Convolutional Codes (SCCC) and other Turbo-Like Codes (TLC). Although regular convolutional codes and TLCs differ significantly in terms of performance, structure and decoding techniques, their decoders share some common features.
The decoding structures that are used to decode convolutional codes are based on trellis processing. A trellis is a representation of the state of the encoder state machine unfolded over time. The trellis is used to estimate the state of the convolutional encoder finite state machine over time based on the information attained from the received signal.
As a special case, one could also classify in the same category codes that are based on single parity check codes since they too could be decoded using a trellis based structure. The parity check state machine can be viewed as a 2-state state machine of a convolutional code, with the parity bit being the termination of that code. So a single parity check code of length K could be viewed and decoded as a terminated 2-state recursive convolutional code of length K+1.
The traditional algorithm for decoding the trellis in the case of a convolutional code involves processing one step at a time through the trellis from beginning to end updating the state metrics in the process. The state metrics are updated using branch metrics that are calculated from the observations for the received sequence collected on the receiver. Each path along the trellis is thus associated with a cost that -corresponds to the likelihood of that sequence being transmitted. The decoder then either makes “hard” decisions about the decoded sequence, a process known as Viterbi algorithm, or produces soft metrics that correspond to the likelihood of a bit that was transmitted assuming a particular value, a process known as Soft Output Viterbi Algorithm or SOVA.
In the case of TLCs, the traditional decoding algorithm, which is known as Forward-Backward Algorithm, processes the trellis in both directions updating the state metrics the same way as the Viterbi algorithm. The state metrics from the two passes along with the branch metrics are then used to generate soft outputs for each bit of interest along the trellis. The module that performs this process is called the Soft-In-Soft-Out or SISO module. In the case of the TLCs there is one such SISO module that corresponds to each convolutional code in the encoder and each SISO passes data to the others and the process iterates until some criterion is met, at which time “hard” decisions are made. Such criteria could be the maximum number of iterations was reached, convergence to a solution was achieved, etc.
The challenge in trellis-based processing is its recursive nature. Both in the case of Viterbi decoders and of SISO modules the critical path of the processing is the state-update process. The processing of each step through the trellis depends on the values generated for the previous step (or the next step if processing backwards). This data dependency means that the next step cannot be processed until the previous one is done processing. In the basic approach that also means that the whole trellis has to be processed in series by the same processor.
Some techniques have been developed that allow a designer to break a trellis into sections (such as windows or tiles), thus breaking the process in smaller blocks that could be processed in parallel. The basic concept is described in U.S. Pat. No. 5,933,462 issued to Viterbi. Instead of decoding the entire block of size K, U.S. Pat. No. 5,933,462 describes an algorithm for decoding over a window of size L instead to reduce memory requirements. The concept can be extended in the forward direction as well and used to break the block of size K trellis sections into smaller independent sections of size L.
However, this does not solve the data dependency problem, and current hardware implementations of trellis processors are constrained to be as fast as the execution of the recursive state-update calculations. When designers wish to speed up the process they often use multiple state-update units in parallel for different sections of the trellis, in order to achieve the required speed. However, such an approach has inherent disadvantages. For one thing, parallel state-update units for different sections of the trellis likely require numerous simultaneous memory accesses and that translates into very wide memories and several constraints, in order to guarantee that the accesses yield no collisions. Furthermore, the amount of logic required for the trellis-processing engine increases linearly with the number of these parallel units used.
Therefore, there remains a significant need for more efficient trellis-based decoding techniques. This is especially true in performing state-update calculations, which can involve recursive operations.